#include <cstdio>
#include <iostream>
#include <cstdlib>

using namespace std;

template <class T>
class Node {
    public:
        T value;
        Node *next;
};

template <class T>
class LinearList {
    public:
      LinearList(){
          this->head = new Node<T>();
          this->head->next = NULL;
          this->size = 0;
      };
      ~LinearList();
      void output();
      void insert(int index, const T& t);
      void insert(const T &t);
      T &find(int index) const;
      T &del(int index) const;
      int indexOf(T *t);
      void merge(const LinearList<T> *list);

    private:
      Node<T> *head;
      int size;
};

template <class T>
LinearList<T>::~LinearList() {
    Node<T> *cur = this->head->next;
    while (cur != NULL) {
        Node<T> *tmp = cur->next;
        delete cur;
        cur = tmp;
    }
    delete this->head;
}

template <class T>
void LinearList<T>::output() {
    Node<T> *cur = this->head->next;
    int index = 0;
    while (cur != NULL) {
        cout << cur->value;
        if (index < this->size - 1) {
            cout << ",";
        } else
            cout << endl;
        index++;
        cur = cur->next;
    }
}


template <class T>
void LinearList<T>::insert(int index, const T& t) {
    if (index < 0 || index > this->size) {
        throw exception();
    }
    Node<T> *node = new Node<T>();
    node->value = t;

    int theIndex = 0;
    Node<T> *cur = this->head;
    while (theIndex < index && cur != NULL) {
        theIndex++;
        cur = cur->next;
    }

    Node<T> *next = cur->next;
    cur->next = node;
    node->next = next;

    this->size = this->size + 1;
}

template <class T>
void LinearList<T>::insert(const T &t)
{
	Node<T> *cur = this->head;
	int theIndex = 0;
	while (theIndex <= this->size && cur != NULL && cur->value < t) {
		theIndex++;
		cur = cur->next;
	}
    insert(theIndex - 1, t);
}

template <class T>
T& LinearList<T>::find(int index) const {
    if (index < 1 || index > this->size) {
        return NULL;
    }
    int theIndex = 0;
    Node<T> *cur = this->head;
    while (theIndex < index && cur != NULL) {
        theIndex++;
        cur = cur->next;
    }

    return cur->value;
}

template <class T>
int LinearList<T>::indexOf(T* t) {
    int theIndex = 0;
    if (t == NULL)
        return 0;
    Node<T> *cur = this->head;
	bool flag = false;
    while (theIndex < this->size && cur != NULL) {
        cur = cur->next;
        theIndex++;
        if (cur->value == *t) {
			flag = true;
            cout<< theIndex<<endl;
        }
    }

	if (!flag) cout<<0<<endl;
    return 0;
}

template <class T>
T& LinearList<T>::del(int index) const {
    if (index < 1 || index > this->size)
    {
        return NULL;
    }
    int theIndex = 1;
    Node<T> *cur = this->head->next;
    Node<T> *last = this->head;
    while (theIndex < index && cur != NULL)
    {
        theIndex++;
        cur = cur->next;
        last = last->next;
    }

    T &t = cur->value;
    last->next = cur->next;
    delete cur;

    this->size = this->size - 1;
    return t;
}

template <class T>
void LinearList<T>::merge(const LinearList<T> *list) {
	/*
    int theIndex = 0;
    Node<T> *cur = this->head;
    while (theIndex < this->size) {
        cur = cur->next;
        theIndex++;
    }
    cur->next = list->head->next;
	*/
	Node<T> *cur = list->head;
	//this->size = this->size + list->size;
	int theIndex = 0;
	while (theIndex < list->size) {
		cur = cur->next;
		insert(cur->value);
		theIndex++;
	}
}

int main()
{
    LinearList<int> *list = new LinearList<int>();
    cout << "Input1" << endl;
    int t;
    while (cin>>t) {
        if (t == 0)
            break;
        list->insert(t);
    }
    cout << "Output1" << endl;
    list->output();

    cout << "Input2" << endl;
    cin >> t;
    list->insert(t);

    cout << "Output2" << endl;
    list->output();

    cout << "Input3" << endl;
    cin >> t;

    cout << "Output3" << endl;
    //cout << list->indexOf(&t) << endl;
	list->indexOf(&t);

    cout << "Input4" << endl;
    cin >> t;

    cout << "Output4" << endl;
    //cout << list->indexOf(&t) << endl;
	list->indexOf(&t);

    cout << "Input5" << endl;
    LinearList<int> *list2 = new LinearList<int>();
    while (cin >> t)
    {
        if (t == 0)
            break;
        list2->insert(t);
    }
    cout << "Output5" << endl;
    list2->output();

    list->merge(list2);
    list->output();

    cout << "End" << endl;
    return 0;
}
